Задание
Для дерева, изображенного на рисунке, определите число вершин и рёбер.
На сколько число вершин больше числа рёбер?
Граф содержит: вершин; ребер.
Число вершин больше числа рёбер на .
Решение
Определим по рисунку количество вершин и рёбер графа:
Видим, что
- вершин восемь: \(\displaystyle A{\small,}\)\(\displaystyle B{\small,}\)\(\displaystyle C{\small,}\)\(\displaystyle D{\small,}\)\(\displaystyle E{\small,}\)\(\displaystyle F{\small,}\)\(\displaystyle G{\small,}\)(H{\small,}\) и \(\displaystyle K{\small;}\)
- рёбер – восемь (пронумеровали для удобства)
Значит, число вершин больше числа рёбер на
\(\displaystyle 9-8=1{\small.}\)
На самом деле, для любого дерева верно
Правило
Свойство
В дереве число рёбер на \(\displaystyle 1\) меньше числа вершин.
Ответ: Граф содержит \(\displaystyle 9\) вершин, \(\displaystyle 8\) рёбер. Число вершин больше числа рёбер на \(\displaystyle 1{\small.}\)